Combinatorial Approximation Algorithms for MaxCut using Random Walks

Extracting certainty from uncertainty regret bounded by variation in costs.
Prediction from expert advice is a fundamental problem in machine learning. A major pillar of the field is the existence of learning algorithms whose average loss approaches that of the best expert in hindsight (in other words, whose average regret approaches zero). Traditionally the regret of online algorithms was bounded in terms of the number of prediction rounds. Cesa-Bianchi, Mansour and Stoltz [4] posed the question whether it is be possible to bound the regret of an online algorithm by the variation of the observed costs. In this paper we resolve this question, and prove such bounds in the fully adversarial setting, in two important online learning scenarios: prediction from expert advice, and online linear optimization. 1
The uniform hardcore lemma via approximate Bregman projections.

O%28sqrt%28log%28n%29%29 Approximation to SPARSEST CUT in %D5%28n2%29 Time.

The uniform hardcore lemma via approximate Bregman projections.

Better algorithms for benign bandits.
The online bandit problem is a repeated decision making problem, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. The difference in these costs is known as the regret of the algorithm. The term bandit refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information. Perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining Õ( √ T) regret was discovered in this setting. In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of Õ( √ Q), where Q is the total variation in the cost functions. This regret bound shows that it is possible to incur much less regret in a slowly changing environment, and in fact, matches regret bounds that are attainable in the simpler stochastic setting, when the cost functions are obtained from a probability distribution. This regret bound, previously conjectured to hold in the full information case, is surprisingly attainable even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling. 1
Better algorithms for benign bandits.
The online bandit problem is a repeated decision making problem, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. The difference in these costs is known as the regret of the algorithm. The term bandit refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information. Perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining Õ( √ T) regret was discovered in this setting. In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of Õ( √ Q), where Q is the total variation in the cost functions. This regret bound shows that it is possible to incur much less regret in a slowly changing environment, and in fact, matches regret bounds that are attainable in the simpler stochastic setting, when the cost functions are obtained from a probability distribution. This regret bound, previously conjectured to hold in the full information case, is surprisingly attainable even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling. 1
Extracting Certainty from Uncertainty Regret Bounded by Variation in Costs.
Prediction from expert advice is a fundamental problem in machine learning. A major pillar of the field is the existence of learning algorithms whose average loss approaches that of the best expert in hindsight (in other words, whose average regret approaches zero). Traditionally the regret of online algorithms was bounded in terms of the number of prediction rounds. Cesa-Bianchi, Mansour and Stoltz [4] posed the question whether it is be possible to bound the regret of an online algorithm by the variation of the observed costs. In this paper we resolve this question, and prove such bounds in the fully adversarial setting, in two important online learning scenarios: prediction from expert advice, and online linear optimization. 1
Noise Tolerance of Expanders and Sublinear Expander Reconstruction.
Abstract We consider the problem of online sublinear expanderreconstruction and its relation to random walks in &#034;noisy &#034; expanders. Given access to an adjacency list representationof a bounded-degree graph G, we want to convert this graphinto a bounded-degree expander G0 changing G as little aspossible. The graph G0 will be output by a distributed filter:this is a sublinear time procedure that given a query vertex, outputs all its neighbors in G0, and can do so even in adistributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the be-havior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small un-known graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander partwill have fast mixing properties, in the general setting of irreducible finite Markov chains. We also design sublineartime procedures to distinguish vertices of the expander part from those in the noise part, and use this procedure in thereconstruction algorithm.
An Expansion Tester for Bounded Degree Graphs.

Computational Equivalence of Fixed Points and No Regret Algorithms

Privacy
Each of two parties PX and P Y holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x; y). That is, PX should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value, f(x; y), and similarly, P Y should not learn any additional information about x.  In this paper we consider two basic questions in the theory of private computations: 1. Which functions can be privately computed ? 2. What is the communication complexity of protocols that privately compute a function  f (in the case that such protocols exist) ? A complete combinatorial characterization of privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1  g(n)  2 \Delta 2  n  there are functions that can be privately...
A combinatorial%2C primal%2Ddual approach to semidefinite programs.
Semidefinite programs (SDP) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as Sparsest Cut and Balanced Separator in undirected and directed weighted graphs, and the Min UnCut problem, this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. 1
Efficient aggregation algorithms for probabilistic data.
Abstract We study the problem of computing aggregation op-erators on probabilistic data in an I/O efficient manner. Algorithms for aggregation operators such as SUM, COUNT, AVG, and MIN/MAX are crucial to applicationson probabilistic databases. We give a generalization of the classical data stream model to handle probabilisticdata, called probabilistic streams, in order to analyze the I/O-requirements of our algorithms. Whereas thealgorithms for SUM and COUNT turn out to be sim-ple, the problem is harder for both AVG and MIN/MAX.Although data stream algorithms typically use randomness, all of the algorithms we present are deterministic.For MIN and MAX, we obtain efficient one-pass datastream algorithms for estimating each of these quantities with relative accuracy (1 + &amp;quot;), using constant up-date time per element and O ( 1 &amp;quot; lg R) space, where eachelement has a value between 1 and R. For AVG, wepresent a new data stream algorithm for estimating its value to a relative accuracy (1 + ffl) in O(log n) passesover the data with O ( 1 &amp;quot; log2 n) space and update time O ( 1 &amp;quot; log n) per element. On the other hand, we provea space lower bound of \Omega ( n) for any exact one-passdeterministic data stream algorithm. Complementing this result, we also present an O(n log2 n)-time exactdeterministic algorithm which uses O(n) space (thus re-moving the data-streaming restriction), improving dramatically on the previous O(n3)-time algorithm. Ouralgorithms for AVG involve a novel technique based ongenerating functions and numerical integration, which may be of independent interest.Finally, we provide an experimental analysis and show that our algorithms, coupled with additionalheuristics, have excellent performance over large data sets.
A combinatorial%2C primal%2Ddual approach to semidefinite programs.
Semidefinite programs (SDP) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as Sparsest Cut and Balanced Separator in undirected and directed weighted graphs, and the Min UnCut problem, this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. 1
Testing Expansion in Bounded Degree Graphs.
We consider testing graph expansion in the bounded-degree graph model (as formulated in [1]). Specifically, we refer to algorithms for testing whether the graph has a second eigenvalue bounded above by a given threshold or is far from any graph with such (or related) property. We present a natural algorithm aimed towards achieving the above task. The algorithm is given a (normalized) second eigenvalue bound ! 1, oracle access to a bounded-degree N-vertex  graph, and two additional parameters ffl; ff ? 0. The algorithm runs in time N  0:5+ff  =poly(ffl),  and accepts any graph having (normalized) second eigenvalue at most . We believe that the algorithm rejects any graph that is ffl-far from having second eigenvalue at most   ff=O(1)  , and prove the validity of this belief under an appealing combinatorial conjecture.   Supported by MINERVA Foundation, Germany. 0  1 Brief Introduction  This memo reports partial results regarding the task of testing whether a given bounded-degree graph ...
A variation on SVD based image compression.

Logarithmic regret algorithms for online convex optimization.
Abstract. In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., choose a sequence of points in Euclidean space, from a fixed feasible set. After each point is chosen, it encounters an sequence of (possibly unrelated) convex cost functions. Zinkevich [Zin03] introduced this framework, which models many natural repeated decision-making problems and generalizes many existing problems such as Prediction from Expert Advice and Cover’s Universal Portfolios. Zinkevich showed that a simple online gradient descent algorithm achieves additive regret O (  √ T), for an arbitrary sequence of T convex cost functions (of bounded gradients), with respect to the best single decision in hindsight. In this paper, we give algorithms that achieve regret O(log(T)) for an arbitrary sequence of strictly convex functions (with bounded first and second derivatives). This mirrors what has been done for the special cases of prediction from expert advice by Kivinen and Warmuth [KW99], and Universal Portfolios by Cover [Cov91]. We propose several algorithms achieving logarithmic regret, which besides being more general are also much more efficient to implement. The main new ideas give rise to an efficient algorithm based on the Newton method for optimization, a new tool in the field. Our analysis shows a surprising connection to follow-the-leader method, and builds on the recent work of Agarwal and Hazan [AH05]. We also analyze other algorithms, which tie together several different previous approaches including follow-the-leader, exponential weighting, Cover’s algorithm and gradient descent. 1
A Fast Random Sampling Algorithm for Sparsifying Matrices.
We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the Chernoff-Hoeffding bounds. Despite the simplicity, the approximation is comparable and sometimes better than previous work. Our algorithm computes the sparse matrix approximation in a single pass over the data. Further, most of the entries in the output matrix are quantized, and can be succinctly represented by a bit vector, thus leading to much savings in space. 1
Logarithmic Regret Algorithms for Online Convex Optimization.
Abstract. In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., choose a sequence of points in Euclidean space, from a fixed feasible set. After each point is chosen, it encounters an sequence of (possibly unrelated) convex cost functions. Zinkevich [Zin03] introduced this framework, which models many natural repeated decision-making problems and generalizes many existing problems such as Prediction from Expert Advice and Cover’s Universal Portfolios. Zinkevich showed that a simple online gradient descent algorithm achieves additive regret O (  √ T), for an arbitrary sequence of T convex cost functions (of bounded gradients), with respect to the best single decision in hindsight. In this paper, we give algorithms that achieve regret O(log(T)) for an arbitrary sequence of strictly convex functions (with bounded first and second derivatives). This mirrors what has been done for the special cases of prediction from expert advice by Kivinen and Warmuth [KW99], and Universal Portfolios by Cover [Cov91]. We propose several algorithms achieving logarithmic regret, which besides being more general are also much more efficient to implement. The main new ideas give rise to an efficient algorithm based on the Newton method for optimization, a new tool in the field. Our analysis shows a surprising connection to follow-the-leader method, and builds on the recent work of Agarwal and Hazan [AH05]. We also analyze other algorithms, which tie together several different previous approaches including follow-the-leader, exponential weighting, Cover’s algorithm and gradient descent. 1
Algorithms for portfolio management based on the Newton method.
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio determined in hindsight. These algorithms are the first to combine optimal logarithmic regret bounds with efficient deterministic computability. They are based on the Newton method for offline optimization which, unlike previous approaches, exploits second order information. After analyzing the algorithm using the potential function introduced by Agarwal and Hazan, we present extensive experiments on actual financial data. These experiments confirm the theoretical advantage of our algorithms, which yield higher returns and run considerably faster than previous algorithms with optimal regret. Additionally, we perform financial analysis using mean-variance calculations and the Sharpe ratio. 1.
Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method.

Analysis and Algorithms for Content%2DBased Event Matching.
Content-based event matching is an important problem in large-scale event-based publish/subscribe systems. However, open questions remain in analysis of its difficulty and evaluation of its solutions. This paper makes a few contributions toward analysis, evaluation and development of matching algorithms. First, based on a simplified yet generic model, we give a formal proof of hardness of matching problem by showing its equivalence to the notoriously hard Partial Match problem. Second, we compare two major existing matching approaches and show that countingbased algorithms are likely to be more computationally expensive than tree-based algorithms in this model. Third, we observe an important, prevalent characteristic of real-world publish/subscribe events, and develop a new matching algorithm called RAPIDMatch to exploit it. Finally, we propose a new metric for evaluation of matching algorithms. We analyze and evaluate RAPIDMatch using both the traditional and new metrics proposed. Results show that RAPIDMatch achieves large performance improvement over the tree-based algorithm under certain publish/subscribe scenarios. 1.
0%28sqrt %28log n%29%29 Approximation to SPARSEST CUT in %D5%28n2%29 Time.

